package com.lark.algorithm.train.onChapter.linkedList;

import com.lark.algorithm.common.domain.letcode.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author btmood
 * @version 1.0
 * @apiNote
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 * 示例 2：
 *
 *
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *
 *
 * 提示：
 *
 * 链表中节点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 109
 * @since 2024-05-30 14:38
 */
public class D20240530Q61_旋转链表 {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            ListNode nextNode = head.next;
            head.next = null;
            stack.push(head);
            head = nextNode;
        }
        Deque<ListNode> queue = new ArrayDeque<>();
        while (!stack.isEmpty()) {
            queue.push(stack.pop());
        }
        while (k > 0) {
            queue.push(queue.pop());
            k--;
        }
        ListNode dummyHead = new ListNode(-1, queue.pop());
        ListNode endNode = dummyHead.next;
        while (!queue.isEmpty()) {
            endNode.next = queue.pop();
            endNode = endNode.next;
        }
        endNode.next = null;
        return dummyHead.next;
    }

    /**
     * 初版递归
     * 当k为2e9时，堆栈溢出，失败。
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight2(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        ListNode preEndNode = head;
        while (preEndNode.next.next != null) {
            preEndNode = preEndNode.next;
        }
        ListNode newHead = preEndNode.next;
        newHead.next = head;
        preEndNode.next = null;
        return rotateRight2(newHead, k - 1);
    }

    /**
     * 递归
     * 对k进行处理，只要对k取余，就能保证k只会在一次遍历之内
     * 之前学习循环队列的时候，其实这个办法用的比较多，看到【循环】应该条件反射想起【取余】
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight3(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        int len = 0;
        ListNode curNode = head;
        while (curNode != null) {
            curNode = curNode.next;
            len++;
        }
        k = k % len;
        return re3(head, k);
    }

    public ListNode re3(ListNode head, int k) {
        if (k == 0) {
            return head;
        }
        ListNode preEndNode = head;
        while (preEndNode.next.next != null) {
            preEndNode = preEndNode.next;
        }
        ListNode newHead = preEndNode.next;
        newHead.next = head;
        preEndNode.next = null;
        return re3(newHead, k - 1);
    }

    public static void main(String[] args) {
        D20240530Q61_旋转链表 m = new D20240530Q61_旋转链表();
        ListNode l1 = new ListNode(5);
        ListNode l2 = new ListNode(4, l1);
        ListNode l3 = new ListNode(3, l2);
        ListNode l4 = new ListNode(2, l3);
        ListNode l5 = new ListNode(1, l4);
        System.out.println(l5);
        ListNode listNode = m.rotateRight(l5, 2);
        System.out.println(listNode);
        int[] tenArr = new int[]{1,2,3,4,5,6};
    }

}
